#!/usr/bin/env/python3
# -*- coding: utf-8 -*-

"""
@Time    : 2020/3/5 9:39
@Author  : Chen Liu
@FileName: yanghui_sanjiao.py
@Software: PyCharm
"""

# 帕斯卡三角（Pascal's Triangle）:即杨辉三角

# 帕斯卡三角形是排列成三角形的一系列数字。 在帕斯卡三角形中，每一行的最左边和最右边的数字总是 1。
# 对于其余的每个数字都是前一行中直接位于它上面的两个数字之和。


# 解法一：动态规划，时间和空间复杂度都是O(N^2)
# class Solution:
#     def generate(self, numRows):
#
#         res = []
#         for i in range(1, numRows+1):
#             row = []
#             for j in range(i):
#                 value = None
#                 if i == j+1 or j == 0:
#                     value = 1
#                     print("%d, %d" % (i-1, j))
#                     print(value)
#                 else:
#                     value = res[i - 2][j - 1] + res[i - 2][j]
#
#                 row.append(value)
#             res.append(row)
#
#         return res


# 解法二：递归
class Solution:
    def generate(self, numRows):
        """返回杨辉三角的所有行"""
        if numRows == 0:
            return []
        if numRows == 1:
            return [[1]]

        # 递归
        upper = self.generate(numRows-1)
        upper.append([1]+[upper[-1][i-1] + upper[-1][i] for i in range(1, numRows-1)] + [1])

        return upper

    def getRow(self, rowIndex):
        """只返回杨辉三角的指定行"""
        if rowIndex == 0:
            return [1]

        if rowIndex == 1:
            return [1, 1]

        upper = self.getRow(rowIndex - 1)
        upper = [1] + [upper[i - 1] + upper[i] for i in range(1, rowIndex)] + [1]

        return upper

    def getRow_2(self, rowIndex):
        res = [1]
        for i in range(1, rowIndex + 1):
            res.insert(0, 0)
            for j in range(i):
                res[j] = res[j] + res[j+1]

        return res


if __name__ == "__main__":
    s = Solution()
    # res = s.generate(5)
    res = s.getRow_2(3)
    print(res)
